#include "interval_tree.h"
#include "types.h"
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;

IntervalTree * globalMemTree = NULL;

static bool logOrNot = false;
void logger(const char * s, ...)
{
    if (!logOrNot) {
        return;
    }
    va_list v;
    va_start(v, s);
    vprintf(s, v);
    va_end(v);
}
void enableLog()
{
    logOrNot = true;
}

void IntervalTree::insert(const Interval & new_interval)
{
    if (this == globalMemTree) {
        LOG("MEM insert %llu-%llu", new_interval.start, new_interval.end);
    }
    if (new_interval.start >= new_interval.end) {
        return; // 忽略无效区间
    }
    intervals.push_back(new_interval);
    // 插入后排序并合并，以保持区间的有序性和非重叠性
    std::sort(intervals.begin(), intervals.end(), [](const Interval & a, const Interval & b) { return a.start < b.start; });
    merge();
    if (this == globalMemTree) {
        this->print("MEM: ");
    }
}

void IntervalTree::remove(const Interval & to_remove)
{
    if (this == globalMemTree) {
    LOG("MEM remove %llu-%llu", to_remove.start, to_remove.end);
    }
    if (to_remove.start >= to_remove.end) {
        return; // 忽略无效区间
    }

    std::vector<Interval> newIntervals;
    for (const auto & current : intervals) {
        // Case 1: to_remove 与 current 无交集
        if (to_remove.end <= current.start || to_remove.start >= current.end) {
            newIntervals.push_back(current);
        }
        else {
            // Case 2: to_remove 与 current 有交集
            // 保留 current 在 to_remove 左侧的部分
            if (current.start < to_remove.start) {
                newIntervals.push_back({current.start, to_remove.start});
            }
            // 保留 current 在 to_remove 右侧的部分
            if (current.end > to_remove.end) {
                newIntervals.push_back({to_remove.end, current.end});
            }
        }
    }
    intervals = newIntervals;
    // 虽然删除操作理论上不会产生新的重叠，但为了代码健壮性，可以保留排序和合并
    std::sort(intervals.begin(), intervals.end(), [](const Interval & a, const Interval & b) { return a.start < b.start; });
    merge();
    if (this == globalMemTree) {
        this->print("MEM: ");
    }
}

long long IntervalTree::getTotalSize() const
{
    long long total_size = 0;
    for (const auto & interval : intervals) {
        total_size += (interval.end - interval.start);
    }
    return total_size;
}

void IntervalTree::getDifference(const IntervalTree & target, std::vector<Interval> & offloadIntervalVec, std::vector<Interval> & reloadIntervalVec) const
{
    offloadIntervalVec.clear();
    reloadIntervalVec.clear();
    /* unsigned long long existProcessedPos = intervals.empty() ? 0 : intervals[0].start; */
    /* unsigned long long needProcessedPos = target.intervals.empty() ? 0 : target.intervals[0].start; */
    vector<Interval>::const_iterator existIt = intervals.begin();
    vector<Interval>::const_iterator needIt = target.intervals.begin();
    if (existIt == intervals.end()) {
        reloadIntervalVec = target.intervals;
        return;
    }
    else if (needIt == intervals.end()) {
        offloadIntervalVec = intervals;
        return;
    }
    map<unsigned long long, pair<int, void *>> combineStatusMap;
    for (auto & interval : intervals) {
        if (combineStatusMap.find(interval.start) == combineStatusMap.end()) {
            combineStatusMap[interval.start] = make_pair(1, interval.user);
        }
        else {
            combineStatusMap[interval.start].first += 1;
        }
        combineStatusMap[interval.end].first -= 1;
    }
    for (auto & interval : target.intervals) {
        if (combineStatusMap.find(interval.start) == combineStatusMap.end()) {
            combineStatusMap[interval.start] = make_pair(-1, interval.user);
        }
        else {
            combineStatusMap[interval.start].first -= 1;
        }
        combineStatusMap[interval.end].first += 1;
    }

    string s;
    char buf[50];
    for (auto & v : combineStatusMap) {
        sprintf(buf, "%llu:%2d(%p)", v.first, v.second.first, v.second.second);
        s += string(buf) + " ";
    }
    LOG("comb %s", s.c_str());

    map<unsigned long long, pair<int, void*>> calcMap;
    int sum = 0;
    for (auto & v : combineStatusMap) {
        sum += v.second.first;
        calcMap[v.first] = make_pair(sum, v.second.second);
    }
    s.clear();
    for (auto & v : calcMap) {
        sprintf(buf, "%llu:%2d(%p)", v.first, v.second.first, v.second.second);
        s += string(buf) + " ";
    }
    LOG("calc %s", s.c_str());

    unsigned long long lastStartPos = 0;
    int lastStartVal = 0;
    void * lastStartUser = NULL;
    int lastVal = 0;
    for (auto & v : calcMap) {
        if (v.second.first == lastVal) {
            continue;
        }
        if ((v.second.first == 1 || v.second.first == -1) && v.second.first != lastVal) {
            if (lastVal == -1) {
                LOG("reload %llu - %llu, %p", lastStartPos, v.first, lastStartUser);
                reloadIntervalVec.push_back(Interval(lastStartPos, v.first, lastStartUser));
            }
            if (lastVal == 1) {
                LOG("offload %llu - %llu, %p", lastStartPos, v.first, lastStartUser);
                offloadIntervalVec.push_back(Interval(lastStartPos, v.first, lastStartUser));
            }
            lastStartPos = v.first;
            lastStartVal = v.second.first;
            lastStartUser = v.second.second;
        }
        if (v.second.first == 0 && v.second.first != lastVal) {
            if (lastStartVal == 1) {
                LOG("offload %llu - %llu, %p", lastStartPos, v.first, lastStartUser);
                offloadIntervalVec.push_back(Interval(lastStartPos, v.first, lastStartUser));
            }
            else if (lastStartVal == -1) {
                LOG("reload %llu - %llu, %p", lastStartPos, v.first, lastStartUser);
                reloadIntervalVec.push_back(Interval(lastStartPos, v.first, lastStartUser));
            }
        }
        lastVal = v.second.first;
    }

    string offloadStr; for (auto & interval : offloadIntervalVec) {offloadStr += to_string(interval.start) + "-" + to_string(interval.end) + " ";};
    string reloadStr; for (auto & interval : reloadIntervalVec) {reloadStr += to_string(interval.start) + "-" + to_string(interval.end) + " ";};
    LOG("offload %s, reload %s", offloadStr.c_str(), reloadStr.c_str());
    return;
}

const std::vector<Interval> & IntervalTree::getIntervals() const
{
    return intervals;
}

void IntervalTree::print(const char * msg) const
{
    string str = to_string(getTotalSize());
    for (auto & interval : intervals) {
        char p[20];
        sprintf(p, "%p", interval.user);
        str += " " + to_string(interval.start) + "-" + to_string(interval.end) + "(" + p + ")";
    }
    LOG("%s%s", msg, str.c_str());
}

void IntervalTree::merge()
{
    if (intervals.empty()) {
        return;
    }

    std::vector<Interval> merged;
    merged.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); ++i) {
        Interval & last = merged.back();
        const Interval & current = intervals[i];

        // 如果当前区间与最后一个合并区间重叠或相邻，则合并
        if (current.start <= last.end) {
            last.end = std::max(last.end, current.end);
        }
        else {
            merged.push_back(current);
        }
    }
    intervals = merged;
}
